\phantomsection
\chapter{State of Art} % Main chapter title
\label{c2_state} % For referencing the chapter elsewhere, use \ref{Chapter1} 
\rhead[\emph{State of Art}]{\thepage}
\lhead[\thepage]{\emph{State of Art}}
\section{Indoor Localization}
\label{state_indoor_Localization}
Global Positioning Signal(GPS) is the foundation of outdoor localization, but it is not suitable for indoor localization since it has been proved to be blocked or absorbed by walls or other obstacles. Alternative signals are required. There are already several solutions regarding indoor localization. Among those solutions, WLAN signal, Infra-red, Ultrasonic, radio signal, RFID signal, GSM signal, and Bluetooth signal are taking place of GPS signal. Related method including Proximity Sensing (Using short range pilot signal),Lateration(Position is computed by range measure of known fix point), Angulation(Position is calculated by measuring angle of arriving signal by multiple known fixed station), Dead Reconning (a new position can be calculated from a fixed or known starting point and movements), Fingerprint(position measure generate by previous recorded data).\cite{IndoorPPT}\\ 
The current solutions of indoor localization which based on other signals (Wi-Fi , Infra-red, Ultrasonic, radio, RFID, GSM, or Bluetooth) and infrastructures can be generally divided into two categories: Geometric model based techniques and Fingerprint based techniques.
\subsection{Geometric model based techniques}
This kind of schema calculate the location base on geometric model. Knowledge of Geometric location of infrastructure is essential prerequisite. Then method such as Proximity Sensing (short range detection), Ingulation (measure angle of arriving signal), Lateration (measure time or time difference of arriving signal), Dead reconning (trace of movements from known position)or power-distance mapping can be used to calculate the location where signal received. Those method are highly depend on reliable performance of sensor and accuracy of signal time synchronization and measurement. There are several existing project implementing such schema.
\begin{enumerate}
\item \textit{Rosum's TV-GPS}\cite{TV} is an enhanced GPS position system. The outdoor part still relays on GPS, the indoor part is based on time difference of arrive time of TV signals. it also needs additional hardware for TV transmitter towers to achieve precise time synchronization.
\item \textit{X Positioning System (XPS)} applied by \textit{Skyhook} \cite{skyhook} is the first commercial metropolitan-scale positioning system.  XPS utilize a scan algorithm to detect Wi-Fi access point (AP) and use GPS positioning information aboug known Wi-Fi APs to (reverse) triangulate the position of new detected AP. All data are stored in a reference database and mobile use can make indoor localization base on known Wi-Fi access point position.

\end{enumerate}
\subsection{Fingerprint based technique}\label{def:fingerprint_method}
The mean idea of this schema is to gather signal fingerprint at every place in the area of interest and build a database. The localization is estimated by mapping the new signal fingerprint against to the database.\cite{LIFS} Figure \ref{fig:WiFiFingerPrint} is a demonstration signal fingerprint respect to Wi-Fi signal. There are four Wi-Fi signals, generated by different access point. They are spreading in all Rooms(the boxes, 3 on the left and 2 on the right) and the corridor(the box in the middle, between left and right). Take the red signal(from access point 1) for example. In the up right room the signal is vary strong. In the down right room the signal becomes weaker. In the corridor and the down left room, the signal almost fades. For any specific room, a collection of signal with their distinctive range of strength form a pattern. Consequently, room-level precession localization is achievable by classifying such a signal pattern. The database can be either a real database table or simply a text file. Researches has shown interests on different signal fingerprint.
\begin{figure}
	\centering
		\scalebox{0.5}{\includegraphics{img/wifiFingerPrint}}
		\rule{35em}{0.5pt}
	\caption{Wi-Fi Fingerprint}
	\label{fig:WiFiFingerPrint}
\end{figure}

\begin{enumerate}
\item \textit{FM Indoor Localization} uses radio (FM) signal as the fingerprint to achieve room-level indoor localization.\cite{FMFP} The mapping of new fingerprint is undertaken through searching the nearest reference fingerprint in database regarding the Manhattan Distance of difference FM signal strength. The signal strength in the fingerprint are normalize with mean and standard deviation of a specific number of samples when merging to a single fingerprint. Such that the performance of mapping through Manhattan Distance is improved.

\item \textit{Wi-Fi Positioning for Android}\cite{WifiAndroid} uses Wi-Fi finterpinrt. The paper \cite{WifiAndroid} implements the mapping between Wi-Fi fingerprints with rooms by comparing the mean value of signal strength from all access points available in the room. Reference mean value of signal strength is pre-calculated and stored in the database. Then the mean value of measurement of calculated and compared so as to find a match to determine the label of the room. 

\end{enumerate}
\subsection{Decision of Signal and Method}
Table \ref{table:singalCompare} shows a compare between different signals.("O" means positive and "X" means negative) Extra Hardware indicating whether extra device in the building or for users are needed if new indoor localization system is to be deployed. RFID, Bluetooth, Infra-red, Ultrasonic, and radio signal all need extra hardware for. GSM and Wi-Fi signal are preferable since they don't need any extra hardware. Table \ref{table:methodCompare} shows compare of different methods in requirements of signal generator or receiver. Proximity Sensing, Ingulation, Lateration and Dead reconning need to geometric data of infrastructure of signal generator, such an requirement largely increases the complexity in implementation. Highly reliable sensor is also not feasible in smartphone. The method based on  fingerprint will be a more acceptable solution. If those two conclusions are combined, GSM signal or Wi-Fi signal with Fingerprint method are the candidate of the indoor localization system. Giving the fact that it is more convenient for smart phone to measure Wi-Fi fingerprint, it is safe to conclude that Wi-Fi fingerprint will be an easy approach for indoor localization.
\begin{table}
\centering
    \begin{tabular}{l|l|l}
    \hline
    Signal                             & Extra Hardware in Building & Extra device for user        \\ \hline
    Wi-Fi                              & X              & X                          \\
    RFID , Bluetooth  				   & O 				& X  						 \\
    Infra-red                          & O    		    & O 							\\
    GSM                                & X              & X 						\\
    Ultrasonic, radio                  & O				& O 				\\ \hline
    \end{tabular}
    \caption {Indoor Localization signal Compare}
    \label{table:singalCompare}
\end{table}
\begin{table}
\centering
    \begin{tabular}{l|l|l}
    \hline
    Method                             & Signal Generator & Signal Receiver        \\ \hline
    Proximity Sensing                  & base station location available             & X                          \\
    Lateration  				   		& base station location	available		&  highly reliable sensor  						 \\
    Angulation                          & base station location available 		 &  highly reliable sensor 							\\
    Dead Reconning                      & starting point location available           &  highly reliable movement sensor						\\
    Fingerprint                  		& X									& X 				\\ \hline
    \end{tabular}
    \caption {Indoor Localization method Compare}
    \label{table:methodCompare}
\end{table}
In order to classify pattern in Wi-Fi fingerprints, we consult the reliable and persuasive machine learning algorithm to find the pattern and make predication for location.
\section{WEKA}
For the definition of Machine Learning, it is not necessary to struggle the philosophical or anthropological definition of learning.It is a techniques for finding and describing structural patterns in data, and make predictions from it for new sample. In Machine Lreaning, there are many algorithms, which are methods implement the learning and classification procedure.\cite{wekaDataMining} This project work is meant to compare several learning algorithms and find the suitable solution, such that the room predication accuracy in percentage is high and geometric error in meters is low. In the mean time, the algorithm need to be feasible to be processed in a smartphone . We are not focus on the essential implementation of those machine learning algorithms. There are already mature open source product of implementations of machine learning algorithms. The one we use is called \textit{WEKA}.\\
\label{WEKA_introduction}
Waikato Environment for Knowledge Analysis (\textit{WEKA}) is a software of machine learning workbench with a collection of state-of-art machine learning algorithms.\cite{wekaDataMining} It is a Java open source application implemented by \textit{The University of Waikato}. Meanwhile, all machine learning algorithms are provided as APIs so that integration to other Java based applications is also straightforward. \\
The data that \textit{WEKA} can handle can come in several format, including \textit{csv}, \textit{json} and even direct database query results. The basic format is Attribute-Relation File Format (\textit{arff}). The following code \ref{sample_arff} is a sample of arff file. It briefly shows the construction of machine learning problem. The file contains three parts, \textit{relation}, \textit{attributes} and \textit{data}. \textit{WEKA} takes \textit{class} also an \textit{attribute} but it has to be explicitly clarified. \textit{Relation} is simply a name, and algorithms are supposed to find relation between \textit{attribute} and \textit{class} according to \textit{data}.\\
\begin{lstlisting}[label=sample_arff,caption=sample.arff]
//@relation <relation_name>
@relation relation1

//@attribute <attribute_name> <attribute_fomate>
@attribute attribute1 numeric
@attribute 1c:c6:3c:1f:54:9c numeric

//@attribute <class_name> <class_enumaration>
@attribute ROOM {room1,roo2,...}

@data
//value_of_attribute1,value_of_attribute_2,..,class
1,1,room1
2,2,roo2
\end{lstlisting}
Figure \ref{fig:weka_main} on page \pageref{fig:weka_main} is the main view of \textit{WEKA} where we load the \textit{arff} file or other data source. The main view also provides visualization of data and a selection of attributes. When the \textit{arff} file is loaded, \textit{WEKA} is able to find the relation between attributes and classes regarding the data. Such a precess is called machine learning or classifier training. We refer to training  in the following of the report. The training phase is base on certain machine learning algorithm. Many algorithms can be applied in the training phase. Each algorithm has its own way to interpret the relation between relations and classes.  A trained classifier is used to classify other data which share the same format (same relation name, attribute and class). The result is either a specific class label or a list of classes with their confidence (the probability for this class), depending on the implementation of the algorithms in \textit{WEKA}. Another extraordinary feature from \textit{WEKA} is that the classifier can be preserved in a file, we name it a model. Although it is not a human readable file,  the model can be loaded again to \textit{WEKA} and we can directly get a classifier without consuming extra time to train the classifier with original data. The feature can largely decrees the time to build the classifier. If the original classifier is updateable, we can even retrain the classifier with new data through Java API provided by \textit{WEKA}.
\begin{figure}
	\centering
		\scalebox{0.5}{\includegraphics{img/wekaMain}}
		\rule{35em}{0.5pt}
	\caption{\textit{WEKA} Main View}
	\label{fig:weka_main}
\end{figure}
Figure \ref{fig:weka_classify} on page \pageref{fig:weka_classify}, which shows the "Classify" view of \textit{WEKA}. On this view we can select machine learning algorithm, specify class label and start training. In addition, a testing scenario has to be  specified  in order to perform instant evaluation on the trained classifier. On the figure we use the Randome Tree algorithm(covered later), specified the class to be attribute "ROOM" and choose cross-validation to test the classifier.
\begin{figure}
	\centering
		\scalebox{0.5}{\includegraphics{img/wekaClassify}}
		\rule{35em}{0.5pt}
	\caption{\textit{WEKA} Classify View}
	\label{fig:weka_classify}
\end{figure}
\textit{WEKA} is a vary powerful machine learning tool, and other functions are not elaborated in this report. The function in the above view are sufficient for this report. And this report utilize the mentioned function mainly via API.
\\
\\
\\
This project dedicates to give an easy approach for indoor navigation. We discard the Geometric model based approach because of the complexity of acquiring infrastructure information and the demand of hight accuracy of receiver sensor. The new approach is based on Wi-Fi fingerprint, which can be provided by any smartphone sensor, thus this solution need no extra device other then a smartphone. Then the machine learning algorithms is apply to the measured Wi-Fi fingerprint so that a predication of location can be made. In the next chapters we will introduce and analyse several machine learning algorithms and find a suitable algorithm for the Wi-Fi fingerprint classification.

